package offer;

/**
 * <p>
 * 剑指 Offer 47. 礼物的最大价值
 * </p>
 *
 * @author xiaozuolin
 * @date 2021/9/26 10:19
 */
public class Offer47 {

    /**
     * [1,2,5]
     * [3,2,1]
     *
     * @param grid
     * @return
     */
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        int[][] dp = new int[row][column];
        dp[0][0] = grid[0][0];
        for (int j = 1; j < column; j++) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }
        for (int i = 1; i < row; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < column; j++) {
                dp[i][j] = grid[i][j] + Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        return dp[row - 1][column - 1];
    }
}
